/*
***********************************************************
           Project 1: ECE 527 
               RETIMING 
	       
	   Team Members:
	   Rohit Kulkarni : PSU ID: 966289989
	   Akshay Kotian  : PSU ID: 910189997

***********************************************************
*/

//------INCLUDES-----------------------------
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <ncurses.h>
#include <math.h>

//------DEFINES-----------------------------
#define infinity 9999
#define INPUT_FILE_PATH "/u/kakshay/Desktop/ECE-527/project1/input.txt"
#define num_nodes 100



//------FUNCTION DECLARATIONS-----------------------------
void read_file(void);
void print_graph_info(void);
void init_edge_w(void);
void compute_new_edge_w(void);
void compute_all_pairs_shortest_paths(int, int[num_nodes][num_nodes]);
void compute_W(void);
void compute_D(void);
void build_constraint_graph(void);
void build_retimed_graph(void);
void Init_c(void);


//------GLOBAL VARIABLES-----------------------------
int no_nodes;
int M;
int c;
int no_feas_const = 0;
int computation_time[num_nodes];
int Suv[num_nodes][num_nodes];
int Suv_c[num_nodes][num_nodes];
int W[num_nodes][num_nodes];
int D[num_nodes][num_nodes];
int edge_w[num_nodes][num_nodes];
int edge_w_new[num_nodes][num_nodes];
int const_graph[num_nodes][num_nodes];
int retiming_vector[num_nodes];
int ERROR=0;
int first_iteration=1;

/*****************************************************************************
  Function:     main
  Description:  Program execution starts from main
******************************************************************************/

int main()
{
    int count_iteration=0;
	
	while (!ERROR)
	{
	count_iteration++;
	printf("\nIteration_count=%d\n",count_iteration);
	
	if (first_iteration==1)
	{
	
	init_edge_w();

    read_file();
	
	compute_new_edge_w();
    
    compute_all_pairs_shortest_paths(no_nodes, edge_w_new);
    
    compute_W();
	
    compute_D();
	
	Init_c();
	
	 printf( "\nC= %d\n",c);

    build_constraint_graph();

    compute_all_pairs_shortest_paths(no_nodes + 1, const_graph);

    print_graph_info();
	
	build_retimed_graph();
	
	first_iteration=0;
	}
	
	else
	{
	 c=c-1;
	 
	 printf( "\nC= %d\n",c);
	
    compute_new_edge_w();
    
    compute_all_pairs_shortest_paths(no_nodes, edge_w_new);
    
    compute_W();
	
    compute_D();

    build_constraint_graph();

    compute_all_pairs_shortest_paths(no_nodes + 1, const_graph);

    print_graph_info();
	
	build_retimed_graph();
	} 
	}
    
	return 0;
}



/*****************************************************************************
  Function : input_graph_parameters.cpp
  Description: Take graph parameters as input by reading a text file  
******************************************************************************/

void read_file(void)
{
    int i;
    int buff;
    int char_count = 0;
    int row_index, col_index;


    FILE *input_file = fopen(INPUT_FILE_PATH, "r");                                                                                            
    if(input_file == NULL)  							      {
	printf("\nCould not open input.txt\n");
    }
    else
    {
	fscanf(input_file, "%d", &no_nodes);      
	for(i = 0; i < no_nodes; i++)
	{
	    fscanf(input_file, "%d", &computation_time[i]);      	
	}

	while(!feof(input_file))
	{
	    //Read row and column indices which represent node numbers
	    fscanf(input_file, "%d", &row_index);      	
	    fscanf(input_file, "%d", &col_index);      	
            #ifdef DEBUG
	      printf("Row index = %d  Col index = %d ", row_index, col_index);
	    #endif
            //Now read the weight and store into appropriate place in array
	    fscanf(input_file, "%d", &edge_w[row_index-1][col_index-1]);     
            #ifdef DEBUG	    
	      printf("Weight = %d\n", edge_w[row_index-1][col_index-1]);
	    #endif 
	}
    }										
    
    fclose(input_file); 
}



/*****************************************************************************
  Function : print_graph_info
  Description: Print graph parameters on the console
******************************************************************************/

void print_graph_info(void)
{
    int i, j;

    printf("\n\nNumber of nodes = %d", no_nodes);

    printf("\nComputation Time of nodes = ");
    for(i = 0; i < no_nodes; i++)
    {	
	printf("%d ", computation_time[i]);
    }

    
    printf("\n\nInput Edge Weights in graph G = \n\n");
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", edge_w[i][j]);
	}
	printf("\n\n");
    }

    printf("\n\nEdge  Weights in graph G' = \n\n");
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", edge_w_new[i][j]);
	}
	printf("\n\n");
    }

    printf("\n\nShortest paths all pairs are = \n\n");
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", Suv[i][j]);
	}
	printf("\n\n");
    }
    
    printf("\n\nW matrix  = \n\n");
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", W[i][j]);
	}
	printf("\n\n");
    }

    printf("\n\nD matrix  = \n\n");
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", D[i][j]);
	}
	printf("\n\n");
    }
	
	printf("\n\nERROR=%d\n",ERROR);

    printf("\n\nConstraint graph matrix  = \n\n");
    for(i = 0; i < no_nodes+1; i++)
    {
	for(j = 0; j < no_nodes+1; j++)
	{
	    printf("%d ", const_graph[i][j]);
	}
	printf("\n\n");
    }

    printf("\n\nShortest paths for constraint graph  = \n\n");
    for(i = 0; i < no_nodes+1; i++)
    {
	for(j = 0; j < no_nodes+1; j++)
	{
	    printf("%d ", Suv_c[i][j]);
	}
	printf("\n\n");
    }    


    printf("\n***********************************");
    printf("\n            ANSWER                 ");
    printf("\n***********************************");

    printf("\n\nRetiming vector = \n");
    for(i = 0; i < no_nodes; i++)
    {
        printf("%d   ", retiming_vector[i]); //Suv_c[no_nodes][i]);
    }

    printf("\n\n\n");
}




/*****************************************************************************
  Function : init_edge_w
  Description: Initialize edge weights to infinity for the following:
               -edge_w matrix
               -const_graph
******************************************************************************/

void init_edge_w(void)
{
    int i, j;
    for(i = 0; i < num_nodes; i++)
    {
	for(j = 0; j < num_nodes; j++)
	{
	    edge_w[i][j] = infinity;
	    const_graph[i][j] = infinity;
	}
    }   
}


/*****************************************************************************
  Function : compute_new_edge_w
  Description: Compute edge weights for graph G'
******************************************************************************/

void compute_new_edge_w(void)
{
    int i, j;
    int dmax = 0;

    //---To Compute M = dmax X n---
    //Step1: Compute dmax
    for(i = 0; i < no_nodes; i++)
    {
	if(computation_time[i] > dmax)
	{
	    dmax = computation_time[i];
	}
    }
    //Step 2: Compute M
    M = dmax * no_nodes;
    
    //Step 3: w'(e) = Mw(e) -t(U)
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    if(edge_w[i][j] == infinity)
	    {
		edge_w_new[i][j] = infinity;
	    }
	    else
	    {
		edge_w_new[i][j] = ((M * edge_w[i][j]) - computation_time[i]);
	    }
	}
    }   
}


/*****************************************************************************
  Function : Compute_all_pairs_shortest_paths
  Description: Compute all pairs shortest paths using Floyd Warshall algorithm 
******************************************************************************/

void compute_all_pairs_shortest_paths(int no_of_nodes, int weights[num_nodes][num_nodes])
{
    int i, j, k, u, v;
    int R[num_nodes][num_nodes][num_nodes];   

    for(v = 0; v < no_of_nodes; v++)
    {
	for (u = 0; u < no_of_nodes; u++)
	{
	    R[0][u][v]= weights[u][v];      // R1=w(U,V)
	    #ifdef DEBUG
	      printf("\nWeights[%d][%d] = %d", u, v, weights[u][v]);	    
	    #endif
	}
    }
 
    for (k = 0; k < no_of_nodes; k++) 
    {
	for(u = 0; u < no_of_nodes; u++) 
	{
	    for (v = 0; v < no_of_nodes; v++) 
	    {
		R[k+1][u][v]= R[k][u][v]; 
		if( R[k+1][u][v]> R[k][u][k] + R[k][k][v])
		    R[k+1][u][v]= R[k][u][k] + R[k][k][v];
	    }
	}
    }

    for(k = 0; k < no_of_nodes; k++) 
    {
	for(u = 0; u < no_of_nodes; u++) 
	{
	    if (R[k][u][u] < 0)
	    {
		printf("FALSE: NEGATIVE CYCLE ENCOUNTERED.");
		ERROR=1;
		
		getchar();
		exit(0);
	    }
	}
    }


    if(no_nodes == no_of_nodes)
    {
	//Now copy shortest paths in matrix Suv
	for(i = 0; i < no_of_nodes; i++)
	{
	    for(j = 0; j < no_of_nodes; j++)
	    {
		if(R[no_of_nodes][i][j]>9000 && R[no_of_nodes][i][j] != infinity)
		{
		Suv[i][j] = infinity;
	    }
		else
		{
		Suv[i][j] = R[no_of_nodes][i][j];
		}
	    }
    }
	}

    else
    {	
	//Now copy shortest paths in matrix Suv
	for(i = 0; i < no_of_nodes; i++)
	{
	    for(j = 0; j < no_of_nodes; j++)
	    {
		if(R[no_of_nodes][i][j]>9000 && R[no_of_nodes][i][j] != infinity)
		{
		Suv_c[i][j] =infinity;
		}
		else
		{
		Suv_c[i][j] = R[no_of_nodes][i][j];
	    }
	    }
	}
	}
	//save the last row in the Suv_c matrix as the retiming vector
	for(i = 0; i < no_of_nodes-1; i++)
    {
        retiming_vector[i]= Suv_c[no_of_nodes-1][i];
    }
	
    

    #ifdef DEBUG
    for (k = 0; k < no_of_nodes; k++) 
    {
	for(u = 0; u < no_of_nodes; u++) 
	{
	    for (v=0; v < no_of_nodes; v++) 
	    {
		printf("\n\nR[%d][%d][%d] = %d ", k, u, v, R[k][u][v]);
	    }
	}
    }
    #endif
}


/*****************************************************************************
  Function:     compute_W
  Description:  This function computes W matrix by taking Suv and M as inputs
******************************************************************************/

void compute_W(void)
{
    int i, j;
    float temp;

    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    if(i == j)
	    {
		W[i][j] = 0;
	    }
	    else
	    {
		W[i][j] = ceil((float) Suv[i][j] / M);
	    }
	    
	}
    }       
}

/**************************************************************************
  Function:     compute_D
  Description:  This function computes D matrix by taking Suv, W(U,V), computation_time[V] and M as inputs
***************************************************************************/

void compute_D(void)
{
    int i, j;
	    
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	
	    if(i == j)
	    {
		D[i][j] = computation_time[i];
	    }
	    else
	    {
		D[i][j] = ((M*W[i][j]) - Suv[i][j] + computation_time[j]);
		
		
	    }
	    
	}
    }       
}





/**************************************************************************
  Function:     Init_c
  Description:  This function initialises the value of c by computing the maximum value in the D matrix
***************************************************************************/

void Init_c(void)
{
    int i, j;
	c= D[0][0];
    
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	
		if(c<D[i][j])
		{
			c=D[i][j];
		}
	    
	    
	}
    }       
}



/**************************************************************************
  Function:     build_constraint_graph
  Description:  This function forms the constraint graph by taking inputs as:
                c (computation time constraint)
                W and D
***************************************************************************/

void build_constraint_graph(void)
{
    int i, j;

    //FEASIBILITY CONSTRAINTS
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    if(edge_w[i][j] != infinity)
	    {
	       const_graph[j][i] = edge_w[i][j];	       
	    }	   
	}	
     }

    //CRITICAL PATH  CONSTRAINTS
    for(i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    if(D[i][j] > c)
	    {
	       if(const_graph[j][i] > W[i][j] - 1)
	       {
	          const_graph[j][i] = W[i][j] - 1;
	       }	       
	    }	   
	}	
    }

    //Add one extra node and make weights of edges starting from this node 0
    for(i = 0; i < no_nodes; i++)
    {  
       const_graph[no_nodes][i] = 0;
    }	
}




/***********************************************************************************************
  Function:     build_retimed_graph
  Description:  This function retimes the input graph depending on the values of retiming vector
*************************************************************************************************/

void build_retimed_graph(void)
{
int j,k;

for ( j=0;j<no_nodes; j++)
{
	if(retiming_vector[j]>0)		
	{
	
		for (k=0; k<no_nodes;k++)
		{
			if(edge_w[k][j]!=infinity)		
			{
				edge_w[k][j]-=retiming_vector[j];				//remove a flip flop from input of the node
			}
		
		}
	
		for (k=0; k<no_nodes;k++)
		{
			if(edge_w[j][k]!=infinity)		
			{
				edge_w[j][k]+=retiming_vector[j];		   //add a flip flop to the output of the node
			}
		}
	}
	
	
	if(retiming_vector[j]<0)		
	{
		for ( k=0; k<no_nodes;k++)
	    {
			if(edge_w[j][k]!=infinity)		
			{
				edge_w[j][k]-=retiming_vector[j];				//remove a flip flop from the output of the node
			}
		}
	
		for (k=0; k<no_nodes;k++)
		{
			if(edge_w[k][j]!=infinity)		
			{
				edge_w[k][j]+=retiming_vector[j];		
			}
		}
	}
	
}
	 printf("\n\nRetimed Edge Weights in graph G = \n\n");
    for(int i = 0; i < no_nodes; i++)
    {
	for(j = 0; j < no_nodes; j++)
	{
	    printf("%d ", edge_w[i][j]);
	}
	printf("\n\n");
    }
	}